Tiền thân của đội là Đội bóng đá Phú Khánh, thành lập vào năm 1976. Là đội bóng nghiệp dư đại diện cho tỉnh Phú Khánh, đội bắt đầu tham gia Giải vô địch bóng đá Việt Nam từ năm 1980 và nhiều năm liền đạt thành tích tốt. Tại Giải bóng đá vô địch quốc gia Việt Nam 1987, đội lọt vào vòng bán kết và đạt hạng 4.

Kết thúc Giải phân hạng 1989, đội được xếp vào thi đấu ở Giải A1. Cũng trong năm đó, tỉnh Phú Khánh tách ra thành 2 tỉnh Khánh Hòa và Phú Yên, đội được chuyển về cho tỉnh Khánh Hòa quản lý với tên gọi Đội bóng đá Khánh Hòa. Tại mùa giải 1991, đội đã thi đấu thành công, giành được suất thăng hạng. Tuy nhiên, đội không duy trì được phong độ khi vào mùa giải năm 1992, và phải chấp nhận xuống thi đấu trở lại ở Giải A1.

Đội trở lại thi đấu ở Giải bóng đá vô địch quốc gia Việt Nam 1995 và duy trì được vị trí ở các mùa giải sau đó.

Tại Giải vô địch quốc gia chuyên nghiệp lần đầu tiên mùa bóng năm 2000-01, đội có thành tích tệ nhất giải khi thi đấu 18 trận, chỉ có 7 điểm gồm: 1 trận thắng, 4 trận hòa và 13 trận thua, ghi được 15 bàn thắng và để thủng lưới 36 bàn. Nhưng 15 bàn thắng đó, Đặng Đạo đã chiếm số bàn thắng hơn 1/2 số bàn thắng mà đội ghi được. Kết quả tồi tệ này còn ảnh hưởng tại Giải hạng Nhất mùa bóng 2001-2002. Do bị khủng hoảng cầu thủ, đội có một kết quả thi đấu tồi và nhận kết quả phải xuống thi đấu ở giải hạng Nhì năm sau.

Mùa bóng năm 2004, dưới sự tài trợ của Tổng công ty Khánh Việt của ông bầu Nguyễn Xuân Hoàng, đội thi đấu khá thành công và giành được chức vô địch Giải hạng Nhì, giành được suất thi đấu ở Giải hạng Nhất.

Ngày 1 tháng 11 năm 2004, đội chính thức chuyển sang mô hình câu lạc bộ bóng đá chuyên nghiệp khi Ủy ban Nhân dân tỉnh Khánh Hòa chính thức bàn giao đội bóng cho Tổng Công ty Khánh Việt quản lý với tên gọi mới là Câu lạc bộ bóng đá KHATOCO Khánh Hòa.

Tại giải hạng nhất 2005, đội thi đấu thành công với 41 điểm, trong đó có: 12 trận thắng, 5 trận hòa và 5 trận thua, giành được quyền thi đấu tại V-league. Dù đoạt chức vô địch Giải hạng Nhất, nhưng số trận thắng của đội còn ít hơn cả Tiền Giang.